\documentclass{article}
\usepackage[english]{babel}
\usepackage{xeCJK}

\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usepackage{xcolor}
\usepackage{listings}
\graphicspath{images/}
\title{BST排序算法实现作业报告}
\author{舒开宸}

\begin{document}
\maketitle
\lstset{language=C++}
\lstset{breaklines}%
\lstset{
    numbers=left, 
    numberstyle= \tiny, 
    keywordstyle= \color{ blue!70},
    commentstyle= \color{red!50!green!50!blue!50}, 
    frame=shadowbox, % 阴影效果
    rulesepcolor= \color{ red!20!green!20!blue!20} ,
    escapeinside=``, % 英文分号中可写入中文
    xleftmargin=2em, aboveskip=1em,
    framexleftmargin=2em
}
\section{设计思路}

\subsection{BinarySearchTree.h}
本次作业我使用了教材提供的定义BinarySearchTree类的源代码，并添加了对向量容器进行排序的BSTSorting公有成员函数、用于BSTSorting函数内部调用的私有成员函数InfixOutput，用中序遍历的方式将二叉树的成员由小到大输入至向量容器中。

\subsection{main.cpp}
在main.cpp中我写了类内函数BSTSorting和InfixOutput函数的定义，并定义了类外函数向量容器遍历函数PrintVector和向量元素打乱函数
Disorder。在main函数先用较少的数据量测试排序函数的正确性，再用大量的数据来测试二叉树排序在平均情况和极端情况下的排序效率。


\section{核心函数代码展示}


\subsection{InfixOutput}

\begin{lstlisting}
template<typename Comparable>
void BinarySearchTree<Comparable>::InfixOutput(BinaryNode * & t ,vector<Comparable> &_sub)
{                                
    if(t==nullptr)
        return;
    InfixOutput(t->left,_sub);
    _sub.push_back(t->element);
    InfixOutput(t->right,_sub);
}
\end{lstlisting}
\begin{center}
函数以中序遍历的方式将二叉树元素输入至容器\_sub中
\end{center}

\subsection{Disorder}
\begin{lstlisting}
template<typename Comparable>
void Disorder(vector<Comparable> &_arr)         
{
    srand(time(nullptr));
    for(int i=0;i<_arr.size();i++)
    {
        swap(_arr[i], _arr[rand()%(_arr.size())]);
    }
}
\end{lstlisting}
这段代码运用了ctime库里的函数，从容器的第一个元素遍历至最后一个元素，每次遍历都将当前元素和一个随机元素进行交换，以获得随机序列。

\subsection{BSTSorting}
\begin{lstlisting}
void BinarySearchTree<Comparable>::BSTSorting(vector<Comparable> &_arr, int _mode)
{                                             
    clock_t begin;
    clock_t end;
    if(_mode==1)
        Disorder(_arr); 
    else if(_mode!=0)
    {
        cerr<<"wrong input!"<<endl;
        exit(-1);
    }
    begin=clock();
    for(auto & x:_arr)
        this->insert(x);
    vector<Comparable> sub;
    this->InfixOutput(root,sub);
    end=clock();
    cout<<"the sorting process takes "<<end-begin<<endl;
    swap(sub,_arr);
}
\end{lstlisting}
这段代码测试了BSTsorting的平均效率和最坏情况下的效率，当用户输入1时打乱求平均效率，当用户输入0时对有序序列排序以获得最坏情况的效率，输入其它字符会报错推出程序。调用ctime库里的clock()函数确定排序段代码的运行效率并输出。算法思路是先创建一个临时向量容器变量sub，将\_arr中的元素插入二叉树中，再将二叉树元素用infix-output函数插到sub中，用std标准库的swap函数交换sub和\_arr，就实现了\_arr容器的排序。

\section{主程序以及测试结果}

\subsection{main函数}
\begin{lstlisting}
int main()
{
    /**
     * Object Groot is constructed to test
     * function Disorder and function
     * BSTSorting.
     * 
     */
    BinarySearchTree<int>Groot;
    vector<int> a;
    for(int i=0;i<10;i++)
        a.push_back(i);
    Disorder(a);
    PrintVector(a);
    Groot.BSTSorting(a);
    PrintVector(a);

    /**
     * Object GiantTree is constructed to
     * test the sorting effeciency in 
     * different situations.
     * 
     */
    BinarySearchTree<int> GiantTree;
    vector<int> b;
    int mode,j;
    cin >> mode;
    if(mode==0)
        j=50000;
    if(mode==1)
        j=5000000;
    for(int i=0;i<j;i++) 
        b.push_back(i);
    GiantTree.BSTSorting(b,mode);
        
}
\end{lstlisting}
正确性测试输入0—9,先打乱并输出，然后再排序后并输出。效率测试由于顺序情况插入耗时过长且结果显然，所以取值50000，平均情况耗时短结果不显然，所以取值5000000

\subsection{效率分析}
测定最差情况下的效率，即按顺序输入时，我输入了50000个测试数据平均操作次数为22253602，符合$O(N^2)$的结果。在随机打乱情况下，我输入了5000000个数据，平均操作次数为13576459，与理论上的$O(NlogN)$无特别大出入。
\subsection{测试结果}
为了方便阅读结果，排序正确性测试和排序效率测试被分别测试

\begin{figure}[htp]
    \centering
    \includegraphics{images/1.png}
    \caption{排序函数正确性测试结果}
\end{figure}

\begin{figure}[htp]
    \centering
    \includegraphics{images/2.png}
    \caption{输入错误的测试结果}
\end{figure}

\begin{figure}[htp]
    \centering
    \includegraphics[width=12cm,height=5cm]{images/3.png}
    \caption{最坏情况效率测试结果}
\end{figure}

\begin{figure}
    \includegraphics[width=12cm,height=5cm]{images/4.png}
    \caption{平均情况效率测试结果}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=12cm,height=5cm]{images/5.png}
    \caption{valgrind检查内存泄漏}
\end{figure}

\end{document}
